class Solution(object):
    def getIndex(self, reader):
        n = reader.length()
        left = 0
        right = n - 1
        while left < right:
            m = right - left + 1
            if m % 2 == 1:
                mid = (left + right) // 2
                l_left = left
                l_right = mid - 1
                r_left = mid + 1
                r_right = right
            else:
                mid = (left + right) // 2
                l_left = left
                l_right = mid
                r_left = mid + 1
                r_right = right
            val = reader.compareSub(l_left, l_right, r_left, r_right)
            if val == 0:
                return mid
            if val > 0:
                left = l_left
                right = l_right
            else:
                left = r_left
                right = r_right
        return left

